package com.Sep_Eight;

import java.util.Arrays;

/**
 * 667. 优美的排列 II
 * 给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：
 *
 * 假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
 * 返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/beautiful-arrangement-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution667 {

    /**
     * 寻找规律
     * 思路分析： 这道题就是找规律吧。
     * 当n = 50， k = 20时：
     * [1,21,2,20,3,19,4,18,5,17,6,16,7,15,8,14,9,13,10,12,11,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]
     * 当n = 50，k = 17时：
     * [1,18,2,17,3,16,4,15,5,14,6,13,7,12,8,11,9,10,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50]
     * 当n = 80，k = 30时：
     * [1,31,2,30,3,29,4,28,5,27,6,26,7,25,8,24,9,23,10,22,11,21,12,20,13,19,14,18,15,17,16,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80]
     * 是不是发现了规律，就是
     * 下标从[0, k]中，偶数下标填充[1,2,3…]，奇数下标填充[k + 1, k, k - 1…]，后面[k + 1, n - 1]都是顺序填充
     * @param n
     * @param k
     * @return
     */

    public static int[] constructArray(int n, int k) {
        int[] ans=new int[n];
        int numk=k+1;
        int numTemp=1;
        for (int i=0;i<=k;i+=2)
        {
            ans[i]=numTemp++;
        }
        for (int i=1;i<=k;i+=2)
        {
            ans[i]=numk--;
        }
        for (int i=k+1;i<n;i++)
        {
            ans[i]=i+1;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(constructArray(3, 1)));
    }
}
